package cn.tedu.string;

/**
 * 最长回文子串
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 * 示例 1：
 * <p>
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba" 也是一个有效答案。
 * 示例 2：
 * <p>
 * 输入: "cbbd"
 * 输出: "bb"
 */
public class LongestPalindrome {
    private String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return R - L - 1;
    }

    /**
     * 华为面试时当场做的实现方法
     *
     * @param input
     * @return
     */
    private static String longestPalindrome_Huawei(String input) {
        if (input == null || input.length() == 0)
            return "";
        if (input.length() == 1)
            return input;
        int sLength = 1;
        int start = 0;
        int len = input.length();
        int[][] db = new int[len][len];
        for (int i = 0; i < len; i++) {
            db[i][i] = 1;
            if (i < len - 1 && input.charAt(i) == input.charAt(i + 1)) {
                db[i][i + 1] = 1;
                sLength = 2;
                start = i;
            }
        }
        for (int i = 3; i <= len; i++) {
            for (int j = 0; j + i - 1 < len; j++) {
                int end = i + j - 1;
                if (input.charAt(j) == input.charAt(end)) {
                    db[j][end] = db[j + 1][end - 1];
                    if (db[j][end] == 1) {
                        start = j;
                        sLength = i;
                    }

                }
            }
        }

        String resultStr = input.substring(start, start + sLength);
        return resultStr;
    }

    public static void main(String[] args) {
        LongestPalindrome inst = new LongestPalindrome();
        System.out.println(inst.longestPalindrome("abcba"));
    }
}
